package test.day06;

import java.util.Stack;

public class CollectWater {
	public int trap(int[] height) {
		int max = 0;
		Stack<Integer> stack = new Stack();
		for (int i = 0; i < height.length; i++) {
			// 如果不满足比栈顶元素小，则栈顶元素出栈
			while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
				int top = stack.pop();
				// 将满足条件的全部出栈，直到栈顶元素大于height[i]
				while (!stack.isEmpty() && height[top] == height[stack.peek()]) {
					stack.pop();
				}
				if (!stack.isEmpty()) {
					int tmp = height[stack.peek()];
					int h = Math.min(tmp - height[top], height[i] - height[top]);
					int w = i - stack.peek() - 1;
					max += h * w;
				}
			}

			stack.push(i);
		}
		return max;
	}
}
